Description
给定 ,求下式的值
浅い夢だから 胸をはなれない
给定一棵大小为 n 的树,你需要给树上的点两两配对,对于一组对子 (u,v) ,在树上将 u→v 的路径染色。定义一个配对方案合法当且仅当所有边都有颜色。
求方案数对 109+7 取模。
n≤5×103,2∣n
如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。现在给定一张无自环无重边的无向连通图,求有多少种合法的加边方案,使得加边后原图是张仙人掌图。T 组测试数据。
∑n≤5×105,∑m≤106
给定 n 个整数 a1,a2,⋯,an 以及 n 个整数 w1,w2,⋯,wn 。称 a1,a2,⋯,an 的一个排列 ap1,ap2,⋯,apn 为一个合法排列当且仅当该排列满足:对于任意的 k 和任意的 j ,如果 j≤k ,那么 apj=pk 。定义一个合法排列的权值为 wp1+2wp2+⋯+nwpn 。
你需要求出所有合法排列中的最大权值。如果不存在,输出 -1 。
n≤5×105,ai∈[0,n],∑wi≤1.5×1013